package com.study.dataStructure.sortAlgorithms;

import com.study.dataStructure.util.ArraysUtil;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] nums = ArraysUtil.createRandomArr(200,1000);
        System.out.println(Arrays.toString(nums));
        System.out.println( ArraysUtil.isSort(nums) );
        quickSort(nums,0,nums.length-1);

        System.out.println(Arrays.toString(nums));
        System.out.println( ArraysUtil.isSort(nums) );
    }

    /**
     * 换一种方式的快排实现,以数组首位为基准位
     */
    public static void quickSort(int[] arr,int left,int right){
        int l, r, pivot, temp;
        l = left;
        r = right;
        pivot = arr[left];

        //每一轮交换数组首端的pivot值,都需要保证目标交换值小于原pivot值; 所以需要先由右往左,由右往左,右哨兵停下的位置一定是小于首端pivot的
        // 由于左右哨兵一旦相遇就会停住,不管是否达成大小比较条件,故一定要让右哨兵先行,等左哨兵来跟右哨兵相遇
        //如果是左哨兵是等右哨兵来相遇,左哨兵先行只会在大于pivot的地方停止,右哨兵到此,虽然依旧是大于pivot,但因为已与左哨兵相遇,故会停止;
        while (l<r){
            //右哨兵先行
            while (l<r && arr[r]>=pivot){ //要带上等于号,否则遇上与基准位相等的将陷入死循环
                r--;
            }
            while (l<r && arr[l]<=pivot){ //要带上等于号,否则遇上与基准位相等的将陷入死循环
                l++;
            }
            if(l<r){
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        //一轮交换完,pivot基准位换位置
        if(left<r && pivot > arr[r]){
            arr[left] = arr[r];
            arr[r] = pivot;
        }

        //递归调用前一轮左右哨兵重合点两边的数组
        if(left<r-1){
            quickSort(arr,left,r-1);
        }
        if(right>r+1){
            quickSort(arr,r+1,right);
        }
    }
}
